﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution124
{
    int max = int.MinValue;
    public int MaxPathSum(TreeNode root)
    {


        PreOredr(root);

        return max;
    }
    private void PreOredr(TreeNode root)//中左右
    {
        if (root == null) return;



        //操作一下
        int bigger = PathSum(root.left) + PathSum(root.right) + root.val;

        max = Math.Max(bigger, max);
        Console.WriteLine("root:  " + root.val + "   bigger:   " + bigger);

        PreOredr(root.left);
        PreOredr(root.right);
    }

    private int PathSum(TreeNode root)
    {
        if(root == null) return 0;


        //val可能为负数，可以选择不加入,val负数可以加入，但是总和sum必须为正
        //curSum可能为负数，必须选择不加入
        int curSum = Math.Max(PathSum(root.left), PathSum(root.right)) + root.val;

        return curSum>0? curSum:0;
    }
}
class Program124
{


    static void Main124(string[] args)
    {
        int[] preOrder = { 1,2,3};
        int[] inOrder = {2,1,3};

        Solution105 Solution105 = new Solution105();
        TreeNode root = Solution105.BuildTree(preOrder, inOrder);


        //Solution105.levelOrder(root);
       
        Solution124 sol = new();
        int res = sol.MaxPathSum(root);
        Console.WriteLine(res);

    }
}
